/*
 * @lc app=leetcode id=18 lang=cpp
 *
 * [18] 4Sum
 */
class Solution {
private:
    int getSum(vector<int>& nums, int i, int j, int m, int n) {
        return nums[i]+nums[j]+nums[m]+nums[n];
    }
    int getSum(vector<int>& nums, int j, int m, int n) {
        return nums[j]+nums[m]+nums[n];
    }
    vector<vector<int>> threeSum(vector<int>& nums, int target, int st) {
        int j = st;
        int len = nums.size();
        int sum = 0;
        vector<vector<int>> ret;
        while(j<len) {
            int m = j+1;
            int n = len-1;
            while(m < n) {
                sum = getSum(nums, j,m,n);
                if (sum == target) {
                    ret.push_back({nums[j],nums[m],nums[n]});
                    while(--n>=0 && nums[n]==nums[n+1]);
                    while(++m<len && nums[m]==nums[m-1]);
                } else if (sum > target) {
                    while(--n>=0 && nums[n]==nums[n+1]);
                } else {
                    while(++m<len && nums[m]==nums[m-1]);
                }
            }

            while(++j<len && nums[j]==nums[j-1]);
        }
        return ret;
    }

public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {

        vector<vector<int>> ret;
        int len = nums.size();
        if (len < 4) {
            return ret;
        } 

        sort(nums.begin(), nums.end());

        int i = 0, j;
        int sum = 0;
        while(i < len) {
            auto tmp = threeSum(nums, target-nums[i], i+1);
            for (auto v : tmp) {
                vector<int> r(v);
                r.push_back(nums[i]);
                ret.push_back(r);
            }
            while(++i<len && nums[i]==nums[i-1]);
        }
        return ret;
    }
};

